package lrucache;

//参考leetcode146
//https://leetcode.cn/problems/lru-cache/description/

import java.util.HashMap;
import java.util.Map;

public class MyLRUCache {
    static class DLinkNode {
        public int key;
        public int val;
        public DLinkNode prev;
        public DLinkNode next;

        public DLinkNode() {}

        public DLinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public DLinkNode head;
    public DLinkNode tail;
    public int usedSize; //代表当前双向链表当中, 有效的数据个数
    public Map<Integer, DLinkNode> cache;
    public int capacity; //默认容量

    public MyLRUCache(int capacity) {
        this.head = new DLinkNode();
        this.tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
        cache = new HashMap<>();
        this.capacity = capacity;
    }

    /**
     * 存储元素
     * @param key
     * @param val
     */
    public void put(int key, int val) {
        //1.查找当前的这个key是否存储过
        DLinkNode node = cache.get(key);
        //2.如果没有存储过
        if(node == null) {
            //2.1需要实例化一个节点
            DLinkNode dLinkNode = new DLinkNode(key, val);
            //2.2存储到map
            cache.put(key, dLinkNode);
            //2.3把该节点存到链表尾部
            addToTail(dLinkNode);
            usedSize++;
            //2.4检查当前双向链表的有效数据个数是不是超过了capacity
            if(usedSize > capacity) {
                //2.5超过了, 就需要移除链表头部节点 , 清楚缓存中的元素
                DLinkNode remNode = removeHead();
                cache.remove(remNode.key);
                usedSize--;
            }
        }else {
            //3.如果存储过
            //3.1更新这个key对应的val
            node.val = val;
            //3.2将该节点移动到尾节点
            moveToTail(node);
        }
    }

    /**
     * 访问当前的key
     * 把访问的节点放在尾部
     * @param key
     * @return
     */
    public int get(int key) {
        DLinkNode node = cache.get(key);
        if(node == null) {
            return -1;
        }
        //把最近使用的放在了链表尾部
        moveToTail(node);
        return node.val;
    }

    /**
     * 将节点移到链表尾部
     * @param node
     */
    private void moveToTail(DLinkNode node) {
        //1.删除这个节点
        removeNode(node);
        //2.添加到尾巴节点
        addToTail(node);
    }

    /**
     * 删除节点
     */
    private void removeNode(DLinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


    /**
     * 将节点移到链表头部
     */
    private DLinkNode removeHead() {
        DLinkNode del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
    }

    /**
     * 添加节点到链表尾部
     * @param node
     */
    private void addToTail(DLinkNode node) {
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }
}
